package com.hp.test.interview.sort;

public class RadixSort {

    public static void main(String args[]) {
        int arr[] = {101, 10, 11, 66, 94, 26, 125};
        RadixSort rs = new RadixSort();
        rs.radixSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

    }

    private void countSort(int arr[], int exp) {

        int[] count = new int[10];
        int[] output = new int[arr.length];

        for (int i = 0; i < arr.length; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }

    private int max(int arr[]) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        return max;
    }

    public void radixSort(int arr[]) {

        int max = max(arr);
        for (int exp = 1; exp <= max; exp *= 10) {
            countSort(arr, exp);
        }
    }
}
